#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 2 * N, K = 15;
int need[N][K];
int h[N], e[M], w[M], ne[M], idx;
int dist[N][K];
bool st[N];
int n, m, k;
typedef pair<int, int> pi;
#define x first
#define y second
int f[1 << K], state[N];

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

pi dfs(int u, int fa, int v) {
  pi res(0, -1);
  if (need[u][v]) res.y = 0;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == fa) continue;
    auto t = dfs(j, u, v);
    if (t.y != -1) {
      res.x += t.x + w[i] * 2;
      res.y = max(res.y, t.y + w[i]);
    }
  }
  return res;
}

bool check(int mid) {
  memset(state, 0, sizeof(state));
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < k; ++j) {
      if (dist[i][j] <= mid) state[i] |= 1 << j;
    }
  }
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;

  for (int i = 0; i < 1 << k; ++i) {
    for (int j = 1; j <= n; ++j) {
      f[i | state[j]] = min(f[i | state[j]], f[i] + 1);
    }
  }
  return f[(1 << k) - 1] <= m;
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < k; ++j) {
      scanf("%d", &need[i][j]);
    }
  }
  memset(h, -1, sizeof(h));
  for (int i = 0; i < n - 1; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
    add(b, a, c);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < k; ++j) {
      auto t = dfs(i, -1, j);
      if (t.y != -1) dist[i][j] = t.x - t.y;
    }
  }

  int l = 0, r = 1e9;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l;
  return 0;
}
